Dining Philosophers
A number of Philosophers sit at a table Thinking. When they get hungry the stop thinking and eat, before returning to thinking.
The problem lies in the fact that the philosophers (being poor) have to share the cutlery (forks or chopsticks which every version you wish to think about). There is only sufficient utensils for 1 each, however, to eat they need two. They can only use theirs and the one to their left (they're polite as well).
This is a simple state problem, diners wishing to eat must wait for both utensils to be available. The catch, is that whilst philosopher A is picking up his utensils the philosopher B to their left is picking up theirs, if in rare circumstances this happens all around the table ALL philosophers will have picked up one but will be blocked from picking the second and the whole system becomes deadlocked.
To avoid this deadly embrace, all Philosophers they must agree to pick up the utensils in a specific order.
CDL Solution
Click to enlargeThe Pause Logical Semaphore and Interface are simply used to start/stop the system and the Two Eat/Think Semaphores hold the states of each Philosopher automatically toggling between them. When a Philosopher finishes thinking the Semaphores toggle to allow them to collect two Chopstick Semaphores. When they finish thinking they reset the Chopstick Semaphores and re-toggle the Eat/Think Semaphores.
The crux of the solution is embedded in the request connections to the ChopStick Semaphore.
Odd numbered Philosophers should collect the left utensil then their own
Even numbered Philosophers pick up their's followed by the left one
This repeats all the way round the table, and so loops back at the end.
These connections can be setup using macros:
#define First( X ) ( ((X)%2) ? (X) : (((X)+1)%NP) ) // first cross link
#define Second( X ) ( ((X)%2) ? (((X)+1)%NP) : (X) ) // second cross link
#define Next( X ) ( ((X)+1) % NP ) // next node in sequence wrap at end
These Macros can then be used in the Connection Editor Dialogs to make the required connections
| Signal Connection to Semaphore | Request Connection to Semaphore |
| (put down chopstick - order doesnt matter) | (pick up chopstick - cross linked) |
 |
 |
The CDL solution shown above requires no code apart from a GUI, state Diagnostics generated by each Philosopher to drive the GUI and a random timeouts to mimic the Thinking/Eating processes. And once initiated will self-perpetuate until stopped by the GUI.
NB due to the random Sleep in each method, the Accretion : Num Workers needs to be set to NP.
The Dining Philosophers solution is available as a MSVisual Studio 2005 solution package from the Connective Logic Web site.